/**
 * CoalescedHashTable.java
 * 
 * This class defines a hash table that uses coalesced linking to handle collisions
 * 
 * @author Ray DeCuir
 * @version 1.0
 *
 * @param <K> Generic Key type
 * @param <V> Generic Value type
 */

public class CoalescedHashTable<K,V> implements IHashtable<K, V> {

	// instance variables to hold data about the chaining hash table
	private int entryCount, collisions, regrowCount, probeCount, regrowModifier;
	
	// the regrow / maximum loadfactor for the hash table
	private double loadfactor;
	
	// the backbone of the hash table implementation, 
	private CoalescedEntry<K,V>[] table;
	
	
	/**
	 * Constructor for the CoalescedHashTable object
	 * 
	 * @param initialSize The initial size of the hash table backing structure
	 * @param loadfactor The regrow factor for the hash table implementation
	 */
	@SuppressWarnings("unchecked")
	public CoalescedHashTable(int initialSize, double loadfactor)
	{
		this.loadfactor = loadfactor;
		regrowModifier = 1;
		table = new CoalescedEntry[ initialSize ]; 
		this.collisions = 0;
		this.regrowCount = 0;
		this.probeCount = 0;
		this.entryCount = 0;
	}
	
	
	/**
	 * This method calculates and returns the regrow factor / load factor of the hash table
	 * 
	 * @return The current loadfactor of the hash table
	 */
	@Override
	public double loadfactor() {
		return entryCount / (double) table.length;
	}

	
	/**
	 * This function looks up the value stored in the hash table by a particular key.
	 * The method also returns this value
	 * 
	 * @param Key The key value to lookup
	 * 
	 * @return the Value associated with the key, or null if not found
	 */
	@Override
	public V lookup(K key) 
	{
		int code = key.hashCode();
		int index = Math.abs(code) % table.length;
		
		int holdindex = index;
		while ( index != Math.abs( holdindex - 1 ) % table.length ) 
		{	
			probeCount++;
			CoalescedEntry<K, V> bucket = table[index];
			if ( bucket == null)
			{
				return null;
			}
			else if ( bucket.key.equals(key) )
			{
				return bucket.value;
			}
			else
			{
				if ( bucket.next != -1)
				{
					index = bucket.next;
				}
				else
				{
					return null;
				}
			}
		}
		return null;
	}

	
	/**
	 * This method hashes a particular key and value pair and stores them in the hash table. This 
	 * table implementation uses coalesced linking to handle collisions
	 * 
	 * @param Key The key value to hash
	 * @param Value The value to store in the hash table 
	 * 
	 * @return 0 if the key has not been used to store data in the hashtable
	 * 			1 if the key has already been used
	 * 
	 */
	@Override
	public int insert(K key, V value) 
	{
		int temp = probeCount;
		if (lookup(key) != null)
		{
			return 1;
		}
		probeCount = temp;
		int code = key.hashCode();
		int index = Math.abs(code) % table.length;
		int holdindex;

		CoalescedEntry<K, V> bucket = table[index];
		
		if ( bucket == null)
		{
			table[index] = new CoalescedEntry<K,V>(key, value);
			entryCount++;
			if (loadfactor()> loadfactor) {
				regrow();
				regrowCount++;
			}
			return 0;
		}
		else
		{
			holdindex = index;
			while ( table[index].next != -1 && index != Math.abs( holdindex - 1 ) % table.length  )
			{
				collisions++;
				index = table[index].next;
			}
			bucket = table[index];
		}
		if (bucket != null )
		{
			holdindex = index;
			while ( table[index] != null && index != Math.abs( holdindex - 1 ) % table.length )
			{
				collisions++;
				index = ( index + 1) % table.length;
			}
		}
		table[holdindex].next = index;
		table[index] = new CoalescedEntry<K,V>(key, value);
		entryCount++;
		if (loadfactor() > loadfactor) {
			regrow();
			regrowCount++;
		}
		return 0;
	}

	
	
	/**
	 * This method removes the values from the hashtable that is associated with a specific key 
	 * 
	 * 
	 * @param Key The key of the value to be removed 
	 * 
	 * @return A boolean denoting if a value was removed from the hashtable, true if it has
	 */
	@Override
	public boolean remove(K key) {
		int code = key.hashCode();
		int index = Math.abs(code)  % table.length;
		boolean found = false;
		
		while (!found) 
		{
			CoalescedEntry<K, V> bucket = table[index];
			
			if (bucket == null ) 
                return false;
			
			if (bucket.key.equals(key) )  
			{
				if ( bucket.valid )
				{
					bucket.valid = false;
					entryCount--;
					return true;
				}
				return false;
			} 
			else
			{
				if ( bucket.next != -1)
				{
					index = bucket.next;
				}
				else
				{
					return false;
				}
			}
		}
		return false;
	}
	
	/**
	 * Regrows the backing array for the coalesced hash table to double the size 
	 * of the original plus the regrow modifier
	 * 
	 */
	@SuppressWarnings("unchecked")
	public void regrow()
	{
		CoalescedEntry<K, V>[] oldtable =  table;
	    table = (new CoalescedEntry[(table.length *2) + regrowModifier]);
	    entryCount = 0;
		for (int i = 0; i < oldtable.length; i++) {
			CoalescedEntry<K, V> bucket = oldtable[i];
			if (bucket != null && bucket.valid) 
			{
				insert(bucket.key, bucket.value);
			}
		}	
	}

	
	/**
	 * Sets the regrowModifier for the hashtable, the regrowModifier is used
	 * as a constant to add to the backing array size when the array is regrown
	 * 
	 * 
	 */
	@Override
	public void setRegrowModifier(int modifier) {
		this.regrowModifier = modifier;
	}
	
	
	/**
	 * Returns a boolean denoting if the hash table is empty or not ( contains no values )
	 * 
	 * @return a boolean denoting if a table is empty or not
	 */
	@Override
	public boolean isEmpty() {
		return entryCount == 0;
	}

	
	/**
	 * Gets the number of elements currently stored in the hash table
	 * 
	 * @return The number of elements in the hash table
	 */
	@Override
	public int size() {
		return entryCount;
	}

	
	/**
	 * Gets the number of collisions that occur as elements are inserted into the hash table
	 * 
	 * @return The number of collisions in the hash table implementation
	 */
	@Override
	public int collisions() {
		return collisions;
	}

	
	/**
	 * Gets the number of times the hash table was regrown
	 * 
	 * @return The number of times the table was regrown
	 */
	@Override
	public int regrowCount() {
		return regrowCount;
	}

	
	/**
	 * Gets the number of probes needed to insert elements into the hash table
	 * 
	 * @return The number of probes needed to insert elements into the hash table
	 */
	@Override
	public int probeCount() {
		return probeCount;
	}
	
	
	/**
	 * private inner class that creates a key, value, next object for the coalesced hash table
	 * 
	 * @author Ray DeCuir
	 * @version 1.0
	 *
	 * @param <K> Generic Type for the Key
	 * @param <V> Generic type for the Value
	 */
	@SuppressWarnings("hiding")
	private class CoalescedEntry<K,V>
	{
		// the key
		K key;
		
		// the value
		V value;
		
		// link to the next entry in the array
		int next;
		
		// if the node is still valid
		boolean valid;
		
		
		/**
		 * Constructor for the CoalescedEntry
		 * 
		 * @param key The key for the entry
		 * @param value The value for the entry
		 */
		public CoalescedEntry( K key, V value)
		{
			this.key = key;
			this.value = value;
			this.valid = true;
			next = -1;
		}
	}

}
